import java.util.Scanner;

public class UF {
    // 记录节点元素和该元素所在的分组
    private int[] eleAndGroup;
    // 记录并查集中数据的分组个数
    private int count;

    /**
     * 初始化并查集，以整数标识 (0,n-1)个节点
     * @param n
     */
    public UF(int n) {
        this.count = n;
        this.eleAndGroup = new int[n];

        // 下标对应元素，下标里的值对应的是每个元素对应的分组编号
        for (int i = 0; i < n; i++) {
            this.eleAndGroup[i] = i;
        }
    }

    /**
     * 获取当前并查集中的数据有多少个分组
     * @return
     */
    public int getCount() {
        return count;
    }

    /**
     * 判断并查集中元素p和元素q是否在同一分组中
     * @param p
     * @param q
     * @return
     */
    public boolean connected(int p, int q) {
        if (p < 0 || p >= this.eleAndGroup.length || q < 0 || q >= this.eleAndGroup.length) {
            return false;
        }
        return this.eleAndGroup[p] == this.eleAndGroup[q];
    }

    /**
     * 元素p所在分组的标识符
     * @param p
     * @return
     */
    public int find(int p) {
        if (p < 0 || p >= this.eleAndGroup.length) {
            return -1;
        }
        return this.eleAndGroup[p];
    }

    /**
     * 把p元素和q元素所在分组合并
     * @param p
     * @param q
     */
    public void union(int p, int q) {
        int pMark = find(p);
        int qMark = find(q);
        if (connected(p, q)) {
            // 已经在一个分组不需要合并
            return;
        }
        for (int i = 0; i < this.eleAndGroup.length; i++) {
            if (this.eleAndGroup[i] == qMark) {
                this.eleAndGroup[i] = pMark;
            }
        }

        // 组数减一
        this.count--;
    }

    public static void main(String[] args) {
        System.out.println("请输入并查集中的元素个数");
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        UF uf = new UF(n);
        while (true) {
            System.out.println("请输入要合并的第一个点 (0~"+(n-1)+")");
            int q = sc.nextInt();
            System.out.println("请输入要合并的第二个点 (0~"+(n-1)+")");
            int p = sc.nextInt();
            // 判断 q 和 p 是否在同一组
            if (uf.connected(q, p)) {
                System.out.println(q+" 和 "+p+" 已经在同一组，合并失败");
                continue;
            } else {
                uf.union(q,p);
                System.out.println(q+" 和 "+p+" 合并成功");
            }

            System.out.println("并查集当前组数为 "+uf.getCount());
            System.out.print("分组编号：[");
            for (int i = 0; i < n; i++) {
                System.out.print(uf.eleAndGroup[i]+"  ");
            }
            System.out.println("]");
            System.out.print("对应元素：[");
            for (int i = 0; i < n; i++) {
                System.out.print(i+"  ");
            }
            System.out.println("]");
        }
    }
}
